/*
* File: maze.c
* ------------
* This program solves a maze by recursive backtracking.
*/

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/* NoSolution is returned when a function 
* cannot find a solution to a maze.
*/
#define NoSolution 10000

/* Private function prototypes */

static int ShortestPathLength(pointT pt);
static pointT AdjacentPoint(pointT pt, directionT dir);
static string mapMenu(void);
static void printGroupMembers();

/* Main program */

main(){

	int result;

	InitGraphics();

	printGroupMembers();

	SetPauseTime(0.01);
	ReadMazeMap(mapMenu());

	if (result = ShortestPathLength(GetStartPosition())) {
		printf("Lenght of shortest path is %d steps", result);
	}
	else {
		printf("No solution exists.\n");
	}
}

/*
* Function: ShortestPathLength
* Usage: length = ShortestPathLength(pt)
* -------------------------------
* This function attempts to generate a solution to the current
* maze from point pt.  It returns the shortest length from start pt
* to end pt that solves the maze.
*/

static int ShortestPathLength(pointT pt)
{
	directionT dir;
	int lenght, min;

	if (OutsideMaze(pt)) return (0);
	if (IsMarked(pt)) return (NoSolution);
	min = NoSolution;
	MarkSquare(pt);
	for (dir = North; dir <= West; dir++) {
		if (!WallExists(pt, dir)) {
			if (lenght = ShortestPathLength(AdjacentPoint(pt, dir)) + 1) {
				if (lenght < min){
					min = lenght;
				}
			}
		}
	}
	UnmarkSquare(pt);
	if (min == NoSolution){
		return (NoSolution);
	}
	else{
		return(min);
	}
}

/*
* Function: AdjacentPoint
* Usage: newpt = AdjacentPoint(pt, dir);
* --------------------------------------
* This function returns the pointT that results from moving
* one square from pt in the direction specified by dir.  For
* example, if pt is the point (1,1), AdjacentPoint(pt, East)
* would return the point (2,1).
*/

static pointT AdjacentPoint(pointT pt, directionT dir)
{
	pointT newpt;

	newpt = pt;
	switch (dir) {
	case North: newpt.y++; break;
	case East:  newpt.x++; break;
	case South: newpt.y--; break;
	case West:  newpt.x--; break;;
	}
	return (newpt);
}

/*
* Function: mapMenu
* Usage: filename = mapMenu();
* --------------------------------------
* This function returns the name of the file
* that the user chooses.
*/
static string mapMenu(void){

	int map;

	printf("1. Pathlen\n");
	printf("2. Example\n");
	printf("3. Unmark\n");
	while (TRUE){
		map = GetInteger();
		switch (map){
		case 1: 
			return("pathlen.maz");
		case 2: 
			return("example.maz");
		case 3: 
			return("unmark.maz");
		default: 
			printf("Invalid input\n");
			break;
		}
		if (map < 1 || map > 4);
			break;
	}
}

/*
* Procedure: printGroupMembers
* Usage: printGroupMembers();
* --------------------------------
* This procedure prints the authors of this
* program to screen.
*/
static void printGroupMembers(){

	printf("This program was developed by: ");
	printf("Jim Glansk, S141587, ");
	printf("Henrik Wistbacka, S142066\n");
}
